1036C - Classy Numbers - CodeForces Solution

/*
JAI SHREE KRISHNA
सत्त्वानुरूपा सर्वस्य श्रद्धा भवति भारत। श्रद्धामयोऽयं पुरुषो यो यच्छ्रद्धः स एव स।।
Man is made by his belief. As he believes, so he is.
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
const int mod = 1e9 + 7;
#define endl "\n"
#define debug(x) cout<<x<<endl;
//less_equal for multiset
//greater for descending order
//__builtin_popcountll() no of 1 in binary;
//__builtin_clzll() leading zero
//__builtin_ctzll() trailing zero
ll solve(const string& s , ll pos , ll non_zero , ll smaller)
{
    if (non_zero > 3)
        return 0;
    if (pos == s.size())
        return 1;
    ll res = solve(s , pos + 1 , non_zero , (smaller) ? smaller : (s[pos] != '0'));
    if (smaller)
    {
        res += 9 * solve(s , pos + 1 , non_zero + 1 , 1);
    }
    else
    {
        int val = s[pos] - '0' - 1;
        if (val > 0)
            res += val * solve(s , pos + 1 , non_zero + 1 , 1);
        if (s[pos] != '0')
            res += solve(s , pos + 1 , non_zero + 1 , 0);
    }
    return res;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll t;
    cin >> t;
    while (t--)
    {
        ll l , r;
        cin >> l >> r;
        string x = to_string(l - 1);
        string y = to_string(r);
        cout << solve(y , 0 , 0 , 0) - solve(x , 0 , 0 , 0) << endl;
    }
}